package Offer32;

import java.util.*;

/**
 * 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
 *
 * @time 2021.9.8
 */

public class Text_two {
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2 = new TreeNode(9);
        TreeNode treeNode3 = new TreeNode(20);
        TreeNode treeNode4 = new TreeNode(15);
        TreeNode treeNode5 = new TreeNode(7);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode3.left = treeNode4;
        treeNode3.right = treeNode5;
        List<List<Integer>> lists = new SolutionTwice().levelOrder(treeNode1);
//        System.out.println(lists);
        Iterator<List<Integer>> iterator = lists.iterator();
        List<Integer> list = new ArrayList<>();
        Iterator<Integer> iterator1 = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

/*官方题解，我觉得非常有水平
* 但是我的解法的基本思想与其是一致的，换汤不换药，只是官方题解中利用queue的长度来进行结点的添加，我觉得很奇妙*/
class SolutionTwo {
    public List<List<Integer>> levelOrder(TreeNode root) {
        ArrayList<List<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            /*这里就十分巧妙了，因为题目要求是输出每一层遍历的结果，所以这里的list一定要定义在while循环内部
            因为只有放在内部，才能实现只添加每一层的结点，放在外面就会添加整个二叉树全部的结点，这里我踩坑了*/
            List<Integer> list = new ArrayList<>();
            /*这里也十分的精妙，怎么才能实现只遍历每一层的结点，然后添加进list集合中呢？
            * 这里就给出了答案，作者利用了queue的长度来进行循环，queue的长度是不确定的，但是最长也只是每一层结点的数量，所以利用长度就可以实现遍历每一层的结点*/
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            lists.add(list);
        }
        return lists;
    }
}

/*基于官方题解的个人思想*/
class MyThinking{
    public List<List<Integer>> levelOrder(TreeNode root) {
        ArrayList<List<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            for (int i = queue.size(); i > 0 ; i--) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            lists.add(list);
        }
        return lists;
    }
}

/*二刷*/
class SolutionTwice{
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<List<Integer>> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            List<Integer> list1 = new ArrayList<>();
            for(int i = queue.size(); i>0; i--){
                TreeNode poll = queue.poll();
                list1.add(poll.val);
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if(poll.right != null){
                    queue.add(poll.right);
                }
            }
            list.add(list1);
        }
        return list;
    }
}
